package mo.tags.greedy;

import java.util.ArrayList;
import java.util.List;

public class L767 {

    public String reorganizeString(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c-'a']++;
        }
        int max = Integer.MIN_VALUE;
        int sum = 0;
        int idx = 0;
        for (int i = 0; i < 26; i++) {
            int c = count[i];
            sum += c;
            if (c > max) {
                max = c;
                idx = i;
            }
        }
        if (sum - max < max - 1) {
            return "";
        }

        List<StringBuilder> res = new ArrayList<>();
        for (int i = 0; i < max; i++) {
            StringBuilder tmp = new StringBuilder();
            tmp.append((char) ('a'+idx));
            res.add(tmp);
        }

        int cur = 0;
        int mod = 0;
        while (cur < 26) {
            mod = mod % max;
            if (cur == idx) {
                cur++;
            }
            if (count[cur] != 0) {
                res.get(mod).append((char) ('a'+cur));
                mod++;
                count[cur]--;
            }
            if (count[cur] == 0) {
                cur++;
            }

        }

        StringBuilder merge = res.get(0);
        for (int i = 1; i < max; i++) {
            merge.append(res.get(i));
        }

        return merge.toString();
    }

    public static void main(String[] args) {
        L767 test = new L767();
        System.out.println(test.reorganizeString("vvvlo"));
    }

}
